# -*-coding:utf-8 -*-
import csv
import sys
# sys.setrecursionlimit(100000000) #例如这里设置为一百万

class Point(object):
    def __init__(self,x,y,weigh):
        self.x=x
        self.y=y
        self.weigh=weigh

class DijkstraExtendPath():
    def __init__(self, node_map):
        self.node_map = node_map
        self.node_length = len(node_map)
        self.used_node_list = []
        self.collected_node_dict = {}
    def __call__(self, from_node, to_node):
        self.from_node = from_node
        self.to_node = to_node
        self._init_dijkstra()
        return self._format_path()
    def _init_dijkstra(self):
        self.used_node_list.append(self.from_node)
        self.collected_node_dict[self.from_node] = [0, -1]
        for index1, node1 in enumerate(self.node_map[self.from_node]):
            if node1:
                self.collected_node_dict[index1] = [node1, self.from_node]
        self._foreach_dijkstra()
    def _foreach_dijkstra(self):
        if len(self.used_node_list) == self.node_length - 1:
            return
        for key, val in self.collected_node_dict.items():  # 遍历已有权值节点
            if key not in self.used_node_list and key != to_node:
                self.used_node_list.append(key)
            else:
                continue
            for index1, node1 in enumerate(self.node_map[key]):  # 对节点进行遍历
                # 如果节点在权值节点中并且权值大于新权值
                if node1 and index1 in self.collected_node_dict and self.collected_node_dict[index1][0] > node1 + val[0]:
                    self.collected_node_dict[index1][0] = node1 + val[0] # 更新权值
                    self.collected_node_dict[index1][1] = key
                elif node1 and index1 not in self.collected_node_dict:
                    self.collected_node_dict[index1] = [node1 + val[0], key]
        self._foreach_dijkstra()
    def _format_path(self):
        node_list = []
        temp_node = self.to_node
        node_list.append((temp_node, self.collected_node_dict[temp_node][0]))
        while self.collected_node_dict[temp_node][1] != -1:
            temp_node = self.collected_node_dict[temp_node][1]
            # temp_node+1:因为temp_node是索引，所以加1
            node_list.append((temp_node+1, self.collected_node_dict[temp_node][0]))
        node_list.reverse()
        return node_list
def set_node_map(node_map, node, node_list):
    for x, y, val in node_list:
        node_map[node.index(x)][node.index(y)] = node_map[node.index(y)][node.index(x)] =  val

def get_stir_node():
    stirDescFile = file('pointDesc.csv', 'rb')
    stirDescReader = csv.reader(stirDescFile)

    stir_node = []
    # stir_node.append('0')
    for line in stirDescReader:
        stir_node.append(line[0])
    stirDescFile.close();
    return stir_node;

def get_site_node_map():
    ptpCsvFile = file("ptp.csv", 'rb')
    ptpReader = csv.reader(ptpCsvFile)

    pointDescFile = file('pointDesc.csv', 'rb')
    pointDescReader = csv.reader(pointDescFile)

    # 这个是每一个点坐标和消耗量
    pointLocation = {}
    for line in pointDescReader:
        pointLocation[line[0]] = Point(float(line[1]), float(line[2]), line[3])

    print "pointNum:", len(pointLocation)
    pointDescFile.close()

    ppdistance = []
    num = 1
    for line in ptpReader:
        startLocation = pointLocation[line[0]]
        endLocation = pointLocation[line[1]]
        distance2 = pow(abs(startLocation.x - endLocation.x), 2) + pow(abs(startLocation.y - endLocation.y), 2)
        import math
        distance = math.sqrt(distance2)
        ppdistance.append((line[0], line[1], distance))
        num += 1
        # print line[0],line[1]
    ptpCsvFile.close()
    print '长度：', len(ppdistance)
    return ppdistance

# 获取每个搅拌站的水泥
def get_stir_count():
    weighDescFile = file('stateWeigh.csv', 'rb')
    weighDescFileReader = csv.reader(weighDescFile)
    weigh = {}
    for line in weighDescFileReader:
        # 这里由于是工地的消耗量和搅拌站的数字都是整数
        weigh[line[0]]=int(line[1])
    weighDescFile.close()

    descFile = file('stirState.csv', 'rb')
    descReader = csv.reader(descFile)
    site_count = {}
    for line in descReader:
        site_count[line[0]]=weigh[line[1]]
    descFile.close()

    return site_count;

# 获取工地所需的水泥
def get_site_count():
    pointDescFile = file('pointDesc.csv', 'rb')
    pointDescReader = csv.reader(pointDescFile)
    site_count={}
    for line in pointDescReader:
        site_count[line[0]]=line[3]
    pointDescFile.close
    return site_count

def getShortPath(node_map,start,weigh,stir_weigh):
    min=0;
    point=1;
    for i in range(1, 20, 1):
        # 判断该搅拌站能加?
        stir_key=str(i)
        node_weigh=int(weigh)
        # print "重量",type(node_weigh)
        # print "剩余：",stir_weigh[stir_key]
        if i == 13:
            continue
        if node_weigh < stir_weigh[stir_key]:
            print "哈哈哈哈哈"
            stir_weigh[stir_key] = stir_weigh[stir_key] - node_weigh
        else:
            # print "hehe"
            continue
        print "start:",start,",to:",i
        from_node = node.index(str(start))
        to_node = node.index(str(i))
        dijkstrapath = DijkstraExtendPath(node_map)
        path = dijkstrapath(from_node, to_node)
        print 'path:',path
        if min > path[len(path) - 1][1]:
            min=path[len(path) - 1][1]
            point=i
    return min

def decress(dict,k):
    dict[k]=dict[k]-30

if __name__ == "__main__":
    # 工地站点
    node = get_stir_node()
    # 工地站点路径map
    node_list =get_site_node_map();
    # 工地站点需要的水泥
    # 搅拌站水泥的量

    node_map = [[0 for val in xrange(len(node))] for val in xrange(len(node))]
    set_node_map(node_map, node, node_list)
    # 求各个工地到各个搅拌站的最短距离 存入到一个字典中，key为12，1这样的，value是距离
    # 对这个字典做循环，限制条件是不能超过搅拌站总量，将结果存入到一个字典中
    # A -->; D



    # print len(get_stir_count())
    # print len(get_site_count())
    # 每个工地水泥需求
    site_count=get_site_count()
    print site_count
    # 每个搅拌站生产水泥量
    stir_count=get_stir_count()
    print stir_count
    print "类型：",type(stir_count)
    # for (k,v) in site_count.items():
    #     print k,':',v
    # for (k,v) in stir_count.items():
    #     decress(stir_count,k)
    # for (k,v) in stir_count.items():
    #     print stir_count[k]


    pathCollect = []
    for (site_count_key, site_count_value) in site_count.items():
        min = 1000000;
        point = 1;
        wellPath=[]
        for i in range(1, 20, 1):
            # 判断该搅拌站能加?
            stir_key = str(i)
            node_weigh = int(site_count_value)
            # print "重量",type(node_weigh)
            # print "剩余：",stir_weigh[stir_key]
            if i == 13 or (i==int(site_count_key)):
                continue
            if node_weigh < stir_count[stir_key]:
                print "搅拌站：",stir_key,",",stir_count[stir_key],type(stir_count[stir_key])
            else:
                continue
            print "start:", site_count_key, ",to:", i
            from_node = node.index(str(site_count_key))
            to_node = node.index(str(i))
            dijkstrapath = DijkstraExtendPath(node_map)
            path = dijkstrapath(from_node, to_node)
            print 'path:', path
            if min > path[len(path) - 1][1]:
                # 如果出现比上一个搅拌距离还近的，那么上一个搅拌站的剩余量需要补上这个工地所需量
                if min !=1000000:
                    print "point,",point
                    stir_count[str(point)] = stir_count[str(point)] + node_weigh
                stir_count[str(i)] = stir_count[str(i)] - node_weigh
                min = path[len(path) - 1][1]
                # print min
                point = i
                wellPath=path
        print "min",min
        pathCollect.append([site_count_key,point,min,wellPath])
    # for index in range(len(pathCollect)):
    #     print pathCollect(index)
    # print pathCollect
    for index,value in enumerate(pathCollect):
        print value



    # from_node = node.index('1')
    # to_node = node.index('24')
    #
    # dijkstrapath = DijkstraExtendPath(node_map)
    # path = dijkstrapath(from_node, to_node)
    # print path

    # pathCollect=[]
    # for (site_count_key,site_count_value) in site_count.items():
    #     # print '参量',site_count_value
    #     min=getShortPath(node_map,site_count_key,site_count_value,stir_count)
    #     pathCollect.append(min)
    # print len(pathCollect)
    # print pathCollect
    print "over"





